package demo1;

import java.util.ArrayList;
import java.util.List;

/**
 * 哈诺塔问题
 * https://leetcode.cn/problems/hanota-lcci/submissions/566530458/
 */

class Solution {
    public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
        dfs(A,B,C,A.size());
    }

    private void dfs(List<Integer> a, List<Integer> b, List<Integer> c, int size) {
        // 1. 出口
        if(size == 1) {
            // A上只有一个盘子,直接放到c上
            c.add( a.remove(a.size()-1));
            return;
        }
        // 2. 方法体
        dfs(a,c,b,size - 1);
        c.add( a.remove(a.size()-1));
        dfs(b,a,c,size-1);
    }
}
class Demo {
    public static void main(String[] args) {
        int[] a = new int[] {2,1,0};
        List<Integer> A = new ArrayList<>();
        for(int n : a) A.add(n);
        Solution solution = new Solution();
        List<Integer> B = new ArrayList<>();
        List<Integer> C = new ArrayList<>();
        solution.hanota(A, B, C);
        System.out.println(A);
        System.out.println(B);
        System.out.println(C);
    }
}